//https://leetcode.cn/problems/convert-to-base-2/?envType=daily-question&envId=2024-04-28

class Solution {
public:
    string baseNeg2(int n) {
        if(n==0) return "0";
        vector<string> states={"10","11","00","01"};
        string res;
        while(n){
            int state = (n+2)%4;
            res = states[state]+res;
            n = (n+2)/4 ;
        }
        int start = 0;
        while(res[start]=='0' and start<res.size()-1) start++;
        return res.substr(start,res.size());
    }
};